Quadratic scaling of hashing time

Theory

In Bitcoin a transaction moves money from one address to another and in order to only allow the actual owner of money the ability to move this, we use cryptographic signatures.

An owner of a Bitcoin address can only spend money by adding a cryptographic signature to a transaction that spends it. The act of adding a cryptographic signature includes the hashing of the entire transaction. As such the size of the transaction matters to the speed of this signing, as well as the validation of said signature.

There is a design flaw in Transactions v1, as Satoshi created it, which can lead to the validation of signatures taking longer than expected.

The problem we see is the basic choice Satoshi made about what it means to sign a transaction. The problem is that each signature signs a slightly different version of the entire transaction. And this means that should you have 10 signatures, this means you need to hash the entire transaction 10 times to sign it. People validating those transactions similarly need to hash the entire transaction 10 times, with minor differences between each run.

A natural consequence of this is that adding another input and associated signatures will cause another read and hashing of the transaction. But at the same time it will make the transaction larger and as such make all the existing signature checks take longer.
This makes the amount of work validation takes grow quadratic.

Practice

The actual checking of signatures is incredibly fast. The largest transaction ever mined on mainnet was in block 364292 as reported on reddit.

This will most likely stay the largest transaction based on the protocol limit of 1MB for transactions. Even if we change the block size limits, the transaction size limits (at least for old style transactions) stays.

As such we can conclude this flaw in the design is not really an issue that can be exploited to cripple or somehow cause problems with the network. This is illustrated by the fact that this huge transaction on today's hardware takes 5.5 seconds to validate. On future hardware this will be even faster, and software will likely speed up as well.

Worst case scenario

Some years ago Bitcoin researcher Sergio Demian Lerner posted about the worst case scenario. This setup is 100% meant to exploit the flaw. In a normal usage of Bitcoin this construction has no meaning. The post describes that with the maximum of a 1MB transaction we can end up hashing that one megabyte 19,100 times.

Larger transactions are not allowed, even with larger blocks. This is about the maximum validation time we can reach under attack circumstances.

A simple solution to this worst case scenario is to cache the output of the hashing function. With that the amount of times we actually hash the transaction goes down to less than 100 times.

How does Flexible Transactions solve this?

To be clear, the issue is something we may call solved for all regular purposes. Specifically, there is no danger of people abusing the system to cause a slow down. And this is what most people care about.

It is however still important to address the underlying cause and fix this. We currently have a 1MB transaction limit, and we may want to lift that limit in the future without having to worry about the scaling issue again.

The solution in Flexible Transactions is rather simple and elegant, we replaced repeated hashing of the entire transaction with using the transaction-ID as the basis of signing. This means that the size of the transaction no longer is relevant and we only need to calculate the transaction-ID (txid) once, regardless of the amount of inputs.

This is the same solution that solves the malleability issue.